package cn.dglydrpy.study.algorithm.od;

import java.util.*;

/**
 * @author Yyy
 * @date 2024/11/8 15:23
 * @description
 * 给定一个字符串数组和一个包含万能字符的字符串，判断能否用后者拼写出前者中的单词，求掌握的单词个数。
 *
 * 
输入：
3
apple
car
window
welldoneapplec?
输出：
2
 */
public class Od0026_LeanedWord {
    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
            int n = Integer.valueOf(scanner.nextLine());
            String[] words = new String[n];
            
            for(int i=0;i<words.length;i++){
                words[i] = scanner.nextLine();
            }
            
            String chars = scanner.nextLine();
            
            int ans = myAnswer(words,chars);
            System.out.println(ans);

            int answer1 = answer1(words,chars);
            System.out.println(answer1);

            int answer2 = answer2(words,chars);
            System.out.println(answer2);
        }
    }

    private static int myAnswer(String[] words, String chars) {
        if(words == null || words.length < 1){
            return 0;
        }
        
        if(chars.length() < 1){
            return 0;
        }
        
        int ans = 0;

        char[] chars1 = chars.toCharArray();
        Map<Character,Integer> map = new HashMap<>();
        for(int i = 0;i<chars1.length;i++){
            char c = chars1[i];
            if(map.containsKey(chars1[i])){
               map.put(c,map.get(c)+1);
            }else{
                map.put(c,1);
            }
        }
        
        for(int i=0;i<words.length;i++){
            Map<Character,Integer> tempMap = new HashMap<>(map);
            
            String word = words[i];
            int anyCharCount = (tempMap.get('?') == null) ? 0 : tempMap.get('?');
            for(int j=0;j<word.length();j++){
                if(tempMap.containsKey(word.charAt(j))){
                    Integer count = tempMap.get(word.charAt(j));
                    if(count == 0){
                        anyCharCount--;
                    }else{
                        tempMap.put(word.charAt(j),count-1);
                    }
                }else{
                    anyCharCount--;
                }
                if(anyCharCount < 0){
                    break;
                }
            }
            if(anyCharCount >= 0){
                ans++;
            }
            
        }


        return ans;
    }


    public static int answer1(String[] words, String chars) {

        int matched = 0;
        for (String word : words) {
            if (match(word, chars)) matched++;
        }
        return matched;

    }

    private static boolean match(String word, String chars) {
        if (word.length() > chars.length()) return false;
        List<Character> dictionary = toSortedList(chars);
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (dictionary.contains(c)) {
                remove(dictionary, c);
            } else if (dictionary.contains('?')) {
                remove(dictionary, '?');
            } else {
                return false;
            }
        }
        return true;
    }

    private static void remove(List<Character> list, char c) {
        Iterator<Character> it = list.iterator();
        while (it.hasNext()) {
            if (c == it.next()) {
                it.remove();
                return;
            }
        }
    }

    private static List<Character> toSortedList(String str) {
        List<Character> list = new LinkedList<>();
        for (int i = 0; i < str.length(); i++) {
            list.add(str.charAt(i));
        }
        Collections.sort(list);
        return list;
    }


    public static int answer2(String[] words, String chars) {
        return process(words.length, words, chars);
    }

    public static int process(int n, String[] words, String chars) {
        char[] chs = chars.toCharArray();
        HashMap<Character, Integer> countMap = new HashMap<>();
        // 存储 chars 中每个字符的出现次数
        for (int i = 0; i < chs.length; i++) {
            countMap.put(chs[i], countMap.getOrDefault(chs[i], 0) + 1);
        }
        int ans = 0;
        for (String word : words) {
            // 判断当前单词是否可以用 chars 拼写
            if (match(word, countMap)) {
                ans++;
            }
        }
        return ans;
    }

    public static boolean match(String s, HashMap<Character, Integer> countMap) {
        HashMap<Character, Integer> tmp = new HashMap<>(countMap);
        char def = '?';
        char[] str = s.toCharArray();
        for (int i = 0; i < str.length; i++) {
            char c = str[i];
            Integer count = tmp.get(c);
            if (null == count) {
                count = tmp.get(def);
                c = def;
            }
            if (null == count) {
                return false;
            }
            count--;
            if (count == 0) {
                tmp.remove(c);
            } else {
                tmp.put(c, count);
            }
        }
        return true;
    }
}
